/*
 * @Author: szx
 * @Date: 2022-01-20 15:27:46
 * @LastEditTime: 2022-01-20 15:46:28
 * @Description:
 * @FilePath: \leetcode\100-199\188\188.js
 */
/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (k, prices) {
    if (k == 0) return 0
    const n = prices.length;
    const dp = new Array(n).fill(0).map(() => new Array(k * 2 + 1).fill(0));
    for (let i = 1; i < k * 2; i += 2) dp[0][i] = -prices[0];
    for (let i = 1; i < n; i++) {
        for (let j = 1; j < 2 * k + 1; j += 2) {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
            dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);
        }
    }
    return dp[n - 1][2 * k];
};

console.log(maxProfit(2, [2, 4, 1]))